package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class b7堆排序and小顶堆化 {
	public static void main(String[] args) {
//		int[] arr = new int[] {5,4,3,2,1,1,1};
		int[] arr = new int[] {9,8,6,5,4,7,1,10,15,14,16};//非完全二叉树也行
		long before = System.currentTimeMillis();
		heapSort(arr);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 小顶堆的堆排序---输出结果是从大到小
	 * 如果输出小顶堆这个和数组，是“宏观上从小到大”
	 * O(NlogN)
	 * @param arr
	 */
	public static void heapSort(int[] arr) {
		makeMinHeap(arr);//先建小顶堆
//		for (int i = 0; i < arr.length; i++) {//测试：打印数组---小顶堆
//			System.out.print(arr[i] + " ");
//		}
//		System.out.println();
		for (int i = arr.length - 1; i > 0; i--) {//开始循环
			swap(arr, i, 0);//当前未排序的“数组片段”的最后一个元素与第一个元素交换
//			MinHeapFixDown(arr, 0, i - 1);//把这个“数组片段”进行一次堆化，让这个“数组片段”符合小顶堆规范
			MinHeapFixDown(arr, 0, i);//把这个“数组片段”进行一次堆化，让这个“数组片段”符合小顶堆规范；传入的length代表我要堆化的数组的索引最大值是length-1
		}
	}
	
	/**
	 * 堆化，也称建堆(这里是小顶堆)
	 * @param arr
	 */
	public static void makeMinHeap(int[] arr) {
		for (int i = arr.length / 2 - 1; i >= 0; i--) {//int i = arr.length / 2 - 1;完美找到最合适的开始建堆的时索引，不用担心啦！
			MinHeapFixDown(arr, i, arr.length);
		}
	}
	
	/**
	 * 小顶堆的一次堆化----堆化的核心
	 * @param arr
	 * @param root
	 * @param length//传入的length代表我要堆化的数组的索引最大值是length-1
	 */
	public static void MinHeapFixDown(int[] arr, int root, int length) {
		//设置左右孩子的索引
		int childLeft = root * 2 + 1;
		int childRight = root * 2 + 2;
		//判断左右孩子是否越界
		if (childLeft >= length) {//左孩子越界，右孩子一定越界
			return;//直接返回空；这里也是递归出口之一
		}
		//设置最小值的索引,因为能到这一行左孩子一定没越界，所以先假设左孩子是最小值
		int min = childLeft;//TODO 这个小细节一定要注意啊！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
		if (childRight >= length) {//经过上面的判断，左孩子一定没越界，这里单独判断右孩子的情况
			min = childLeft;//右孩子越界，那么只有一个孩子就是左孩子，那么初始化最小值就只能是左孩子
		} else {//右孩子没越界
			if (arr[childRight] <= arr[childLeft]) {//比较两个孩子的值
				min = childRight;//min永远指向值小的孩子
			}
		}
		//进行根与孩子的比较
		if (arr[root] <= arr[min]) {//如果root比所有孩子都小，那么就构成小顶堆的定义
			return;//无需进行交换；这里也是递归的出口之一
		}
		swap(arr, root, min);//不构成定义，那就交换呗
		MinHeapFixDown(arr, min, length);//然后在把交换后的这条分支，进行递归操作
	}
	
	public static void preOrder(int[] arr, int root) {
		if (root >= arr.length) {
			return;
		}
		System.out.print(arr[root] + " ");
		preOrder(arr, root * 2 + 1);
		preOrder(arr, root * 2 + 2);
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
